package h0907.sort;

import java.util.Arrays;

/**
 * @author 不知名帅哥
 * @version 1.0
 * @description 插入排序
 * @date 2024/9/7 20:41
 */
public class InsertSort {
    public static void main(String[] args) {
        int[] nums = {4, 7, 2, 3, 4};
        insertSort(nums);
        System.out.println(Arrays.toString(nums));
    }

    private static void insertSort(int[] nums) {
        int n = nums.length;
        //默认第一个元素有序
        for (int i = 1; i < n; i++) {
            int key = nums[i];
            //前面有序数组的最后末尾元素的下标
            int j = i - 1;
            while (j >= 0 && nums[j] > key) {
                //往后挪一个位置
                nums[j + 1] = nums[j];
                j--;
            }
            nums[j + 1] = key;
        }
    }
}
